public class Leetcode {
}

//leetcode:55:跳跃游戏
class Solution1 {
    public boolean canJump(int[] nums) {
        int left = 0 ,right = 0, maxPos = 0,n = nums.length;
        while(left <= right){
            //如果跳跃后的最大长度是大于数组长度的，就代表可以跳到最后一个位置
            if(maxPos >= n-1){
                return true;
            }
            //得到这个区间的最大跳跃长度
            for(int i = left; i <= right; i++){
                maxPos = Math.max(maxPos,nums[i] + i);
            }
            //移到新的区间
            left = right + 1;
            right = maxPos;
        }
        return false;
    }
}

//leetcode:45:跳跃游戏II
class Solution2 {
    public int jump(int[] nums) {
        int left = 0 , right = 0 ,ret = 0, maxPos = 0 , n = nums.length;
        while(left <= right){
            if(maxPos >= n-1){
                return ret;
            }
            for(int i = left; i <= right; i++){
                maxPos = Math.max(maxPos,nums[i] + i);
            }
            //记录次数
            ret++;
            left = right + 1;
            right = maxPos;
        }
        return -1;
    }
}